显然,题目求的是:
An Ac a day, keeps the doctor away!
这道题用后缀自动机可以暴力解决。
建好后缀自动机后 , 因为起点到后缀自动机上的每一个点都是一个本质不同的子串 , 我们就可以在 DAWG 上 dp 。 dp[u]表示包含转移u的子串数量,很容易列出转移式:
一道后缀自动机的板题。
我们从根结点开始匹配,如果有转移就将cnt++
不然就顺着后缀链接向上跳,直到找到有转移的点,用 Maxlen 继续匹配。(后缀链接一定是它的子串,也能被匹配)。
这道题用后缀自动机可以暴力解决。
建好后缀自动机后 , 因为起点到后缀自动机上的每一个点都是一个本质不同的子串 , 我们就可以在 DAWG 上 dp 。 dp[u]表示包含转移u的子串数量,很容易列出转移式:
不难发现到f[i]就是长度为 i 子串的 ∣endpos∣ 的最大值。
根据一个性质后缀自动机的一个点的 endpos 被他的后继分为了很多部分,所以我们可以用parent树dp,处理出它的∣endpos∣。
接着是统计答案,显然我们可以用线段树覆盖。
这道题像我这样的 dp 蒟蒻都能一眼看出 dp 式:
设 sum 为 c 的前缀和,则有
各位大佬都用的 wqs 二分,蒟蒻介绍一种简单方法。
dp 式很好列: